1. Field
Exemplary embodiments relate to a method and apparatus for solving a discrete logarithm problem, and more particularly, to a method and apparatus for efficiently solving a discrete logarithm problem that can be widely used in a public key encryption system using a pre-computation table.
2. Description of the Related Art
A public key encryption system calculates a public key and a secret key by using a one-way function that is difficult to solve mathematically. The public key is publicized for anyone to access, whereas the secret key is kept and may be accessed only by users who keep the secret key. Thus, a user who has the publicized public key of the other party can secretly communicate with the other party.
The most common problem in the public key encryption system is a discrete logarithm problem. The discrete logarithm problem defined on a finite field will now be briefly described.
A cyclic group G is a set consisting of remainders in division of a finite field Zp by a prime p under multiplication modulus. More specifically, all elements of the finite field Zp can be generated by iterative multiplication. If g is a generator of the cyclic group G of order q of a multiplication group Zp* of the finite field Zp, an element of the cyclic group G is in the form of gk mod p for a number k (0≦k<(order of G)).
Therefore, the discrete logarithm problem defined in the finite field Zp is to find the number k satisfying y=gk mod p when an element y is given. This is known as a problem that is difficult to be solved computationally with respect to a sufficiently large p. Thus, public key encryption systems of various forms may be designed by using k as a user's secret key and using y=gk mod p as a public key corresponding to the user's secret key k.